package org.example.leetCode;

/**
 * @author Vader
 * @date 2021/12/27
 **/
public class NumFriendRequests {

    public static void main(String[] args) {
        int[] ages = {20, 30, 100, 110, 120};
        System.out.println(numFriendRequests(ages));
    }

    public static int numFriendRequests(int[] ages) {
        quickSort(ages, 0, ages.length-1);

        int big = 0;
        int num = 0;
        for (int i = 0; i < ages.length; i++) {
            int age = ages[i];
            if (age > 100) {
                big++;
                continue;
            }
            int index = i + 1;
            while (index < ages.length) {
                if ((age * 0.5 + 7) < ages[index]) {
                    num++;
                } else {
                    break;
                }
            }
        }
        if (big > 1) {
            num = num + (big * (big - 1)) / 2;
        }
        return num;
    }

    private static void quickSort(int[] ages, int left, int right) {
        if (left > right) {
            return;
        }
        int temp = ages[left];

        int i = left;
        int j = right;

        while (i < j) {
            while (ages[j] >= temp && i < j) {
                j--;
            }
            while (ages[i] <= temp && i < j) {
                i++;
            }

            int exc = ages[i];
            ages[i] = ages[j];
            ages[j] = exc;
        }
        ages[left] = ages[i];
        ages[i] = temp;
        quickSort(ages, left, i - 1);
        quickSort(ages, i + 1, right);
    }
}
